package 算法部分.树;

import java.util.*;

/**
 * 层次遍历 奇数偶数层打印顺序不同
 *
 * @Author idea
 * @Date created in 8:16 下午 2020/4/25
 */
public class BinaryTreeDemo {

    TreeNode root;

    class TreeNode {
        int val;

        TreeNode leftNode;

        TreeNode rightNode;

        TreeNode(int v) {
            this.val = v;
            this.leftNode = null;
            this.rightNode = null;
        }
    }

    public void insertTreeNode(int val) {
        TreeNode newNode = new TreeNode(val);
        if (root == null) {
            root = newNode;
        }
        TreeNode temp = root;
        TreeNode parentNode = root;
        while (true) {
            if (val < temp.val) {
                parentNode = temp;
                if (temp.leftNode == null) {
                    parentNode.leftNode = newNode;
                    break;
                }
                temp = temp.leftNode;
            } else if (val > temp.val) {
                parentNode = temp;
                if (temp.rightNode == null) {
                    parentNode.rightNode = newNode;
                    break;
                }
                temp = temp.rightNode;
            } else {
                return;
            }
        }
    }

    /**
     * 层次遍历 但是这种层次遍历缺乏灵活性
     */
    public void display() {
        System.out.println("输出节点信息");
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> linkedList = new LinkedList();
        linkedList.add(root);
        TreeNode currentNode = root;
        List<Integer> valList = new ArrayList<>();
        valList.add(root.val);
        while (!linkedList.isEmpty()) {
            currentNode = linkedList.poll();
            if (currentNode.leftNode != null) {
                valList.add(currentNode.leftNode.val);
                linkedList.add(currentNode.leftNode);
            }
            if (currentNode.rightNode != null) {
                valList.add(currentNode.rightNode.val);
                linkedList.add(currentNode.rightNode);
            }
        }
        for (Integer val : valList) {
            System.out.println(val);
        }
    }


    /**
     * 第二版本的层次遍历 奇数从左到右 偶数从右到左
     */
    public void displayV2() {
        System.out.println("输出节点信息");
        List<List<Integer>> levels = new ArrayList<>();
        if (root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 0;
        int level_len = 0;
        while (!queue.isEmpty()) {
            levels.add(new ArrayList<>());
            level_len = queue.size();
            for(int i =0 ;i < level_len; i++){
                TreeNode node = queue.remove();
                levels.get(level).add(node.val);
                if(node.leftNode!=null){
                    queue.add(node.leftNode);
                }
                if(node.rightNode!=null){
                    queue.add(node.rightNode);
                }
            }
            level++;
        }
        for(int i =0 ;i<levels.size();i++){
            List<Integer> list = levels.get(i);
            if((i+1)%2==0){
                Collections.reverse(list);
                System.out.println(list);
            }else{
                System.out.println(list);
            }
        }

    }

    public static void main(String[] args) {
        BinaryTreeDemo binaryTreeDemo = new BinaryTreeDemo();
        binaryTreeDemo.insertTreeNode(8);
        binaryTreeDemo.insertTreeNode(4);
        binaryTreeDemo.insertTreeNode(12);
        binaryTreeDemo.insertTreeNode(3);
        binaryTreeDemo.insertTreeNode(6);
        binaryTreeDemo.insertTreeNode(10);
        binaryTreeDemo.insertTreeNode(16);
        binaryTreeDemo.insertTreeNode(2);
        binaryTreeDemo.insertTreeNode(5);
        binaryTreeDemo.displayV2();
    }
}
